1. Field of the Invention
The present invention relates generally to systems and methods for encoding and decoding variable length codes. In particular, the present invention relates to a system and a method for decoding bitstreams of variable length codes.
2. Description of the Related Art
Variable length coding (VLC) is well known in the areas of compression and transmission of digital data and is used to reduce the number of binary bits required to represent information. The basic idea behind variable length coding is very simple: in a binary representation of symbols in a given sequence of symbols, the more frequently used symbols should be represented by shorter binary codes, giving rise to the concept that different symbols ought to be represented by binary codes of different lengths, thus variable length codes. To illustrate the concept, assuming that a message consists of the following sequence of symbols: {a, b, a, c, b, c, a, a, a, c, c, a, b, a, c, b, c, a, a, b }. In this sequence, the message is represented by an alphabet of three letters. The relative frequency of the three symbols is:
frequency_a=9/20=0.45
frequency_b=1/4=0.25
frequency_c=3/10=0.3
Variable length coding replaces each letter by a binary sequence. Using the concept of VLC described above, letter xe2x80x98axe2x80x99 should be represented by the shortest binary sequence: say, xe2x80x980xe2x80x99, letter xe2x80x98cxe2x80x99 should be the next shortest binary sequence xe2x80x9801xe2x80x99, letter xe2x80x98bxe2x80x99 should be the longest, say, xe2x80x98010xe2x80x99. Such a scheme attempts to minimize the number of bits used to represent the symbol taking into consideration their frequency of presence in the sequence. The binary sequence used to represent the symbols is called a codeword. With this representation, the sequence is represented as the bit string {001000101001000010100100010100100010}. One problem with this representation is that in order to recover the original message from the above, without knowing what the original message is, we may have reconstructed (decoded): {a, c, a, a, c, c, a. c . . . }. This is clearly different from the original. The reason is that the letter xe2x80x98bxe2x80x99 can also be interpreted as letter xe2x80x98cxe2x80x99 followed by xe2x80x98axe2x80x99. In other words, the binary representation of letter xe2x80x98cxe2x80x99 is a prefix of letter xe2x80x98bxe2x80x99. To avoid this problem, all variable length codes must be of the so called prefix code, namely, no variable length code can be the prefix of another variable length code. In the above example, we can use the following representation:
xe2x80x98axe2x80x99xe2x86x92xe2x80x980xe2x80x99, xe2x80x98bxe2x80x99xe2x86x92xe2x80x98100xe2x80x99, xe2x80x98cxe2x80x99xe2x86x92xe2x80x9811xe2x80x99.
With this set of variable length codes, the message""s binary representation becomes: {010001110011000111101000111001100100}. One can easily see from that the above binary sequence can be reverted uniquely back to the original message.
Another problem with variable length codes is the efficiency of the representation. Using the same example, we see that if we use:
xe2x80x98axe2x80x99xe2x86x92xe2x80x980xe2x80x99, xe2x80x98cxe2x80x99xe2x86x92xe2x80x9810xe2x80x99, xe2x80x98bxe2x80x99xe2x86x92xe2x80x9811xe2x80x99xe2x80x83xe2x80x83(EQ 1)
that is another prefix code, the message can be represented by fewer number of bits: {0110101110000101001101011100011}. There are many way store present symbols using VLC. In addition, mathematically it is possible to create VLCs that are most efficient (i.e., no other VLC can be more efficient in terms of the number of bits used). In general, VLCs used in compression are aimed at the most optimal VLC representation based on the observed relative frequency.
The processing of representing symbols in a given message by variable length codes (VLCs) is called VLC Encoding, or simply VLE. The reverse process is called VLC Decoding, or VLD. The VLE and VLD are used together to create a more efficient binary representation of a given message at the source and reconstruct the message at the destination. The mapping between the message symbols and the binary sequences must be known by both source and destination beforehand. The mapping is called VLC table. Each VLC table has a number of entries; each entry in the table corresponds to the mapping between the message symbol and the corresponding binary sequence. In the example above, the mapping given in (EQ 1) can be shown in Table 1.
The present invention is described below in the context of methods for VLD. In addition, the following description is limited to VLCs that are of prefix-code type (i.e., no variable length codeword is the partial prefix of another codeword).
A VLD algorithm is the reverse process that maps variable length code back to the original symbols. In compressed video signals such as MPEG-2, for example, many types of information in the elementary stream layer are represented as variable length codes to reduce the number of bits needed to represent the information. In the MPEG-2 decoder, such information must be recovered from the VLC codewords. For the ease of discussion, let""s assume that a codeword, denoted by C, has N number of bits, where N vanes from codeword to codeword. Therefore, a sequence of M codewords can be denoted by {C1, C2, C3, . . . , CM}, where the codeword CM has NM bits. The total number of bits of this sequence is given by:       ∑          l      ≤      m      ≤      M        ⁢      xe2x80x83    ⁢            N      m        .  
In addition, assuming that the codewords are received in the following order: C1 then C2 and so on. Corresponding to these codewords are the original symbols, denoted by xcex11, xcex12, xcex13, . . . , xcex1M, respectively. This can be illustrated as shown in FIG. 5.
Prior art methods decode VLCs by inspecting the codewords one bit at a time as the binary sequence is introduced into the decoder. As the bits are read, the decoder determines which VLC table entries have the matching bit patterns. There may be multiple entries that have partially matching bit patterns. But as more and more bits are read, the number of matching entries reduces, eventually down to a single entry as all bits of the codeword are read. When this last bit is read depends on the length of the codeword. For example, if the codeword has 10 bits, it will take up to 10 binary decisions to reach the final entry that matches the given codeword. To show the above decoding process graphically, the above-described algorithm corresponds to a tree traversing process. An example is shown in FIG. 2. In this example, the VLC table consists of 6 entries, representing 6 symbols, a, b, c, d, e, f. The VLC table is shown in Table 2. (Note that the VLC is of prefix-code type).
In the example shown in FIG. 2, an input codeword has 3 bits: xe2x80x98011xe2x80x99, therefore, as the decoder accepts each bit, it makes a binary decision along the code tree: to traverse left or right. With the first bit being xe2x80x980xe2x80x99, it traverses left, possible decoded symbols are a, b, c, d. With the second bit being xe2x80x981xe2x80x99, it traverses right, possible decoded symbols are reduced to c, d. With the third and last bit being xe2x80x981xe2x80x99, it traverse right, leaving symbol d as the only symbol left. Therefore, after three such decisions, processing steps and memory accesses, it reaches the node d, which is the desired symbol. This is typical with the prior art, thus making VLD generally computationally intensive. Thus, there is a need to simplify or reduce the number of computations need for decoding and thereby reduce the time required for decoding.
Therefore, there is a need for a new system and a new method for performing decoding that is computationally inexpensive.
The present invention overcomes the deficiencies and limitations of the prior art with a system and a method for decoding variable length codes. A preferred embodiment of the system of the present invention comprises a window buffer, a unique variable length code look-up table and a decoder. The window buffer is coupled to receive a bit stream and provides a window output having the same number or more of bits in the longest variable length codeword. The output of the window buffer is coupled to address the variable length code look-up table. The look-up table has entries pre-calculated based on the variable length code book and is pre-stored in the system. The window buffer can have a size of any number of bits from X to Y where X is the number of bits in the longest variable length code and Y is a number greater than X. The output of the variable length code look-up table is provided to the decoder. The output of the variable length code look-up table includes the code specified by the bits, and a number of bits that the window buffer should be incremented. This is in turn used by the decoder to increment the window buffer. The present invention is particularly advantageous because with a modest increase in the size and format of the variable length code look-up table, the decoder in a single memory access can determine at least one code. This can generate significant computational saving particularly when real-time performance must be achieved with limited processor resources.
The method of the present invention for decoding variable length codes preferably comprises the steps of: receiving an input bit stream, defining a window of W bits, read data from memory using the bits in the window, determining whether the data read from memory is a code, generate the code using data read from memory, moving the window by t bits where t is a value read from memory, and repeating the above step until there are no more bits in the bit stream.